package com.zy.recursion;

/**
 * @description: 爬楼梯
 * @author: zhaoyi
 * @create: 2019-09-04 21:34
 * https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memoization/1213/
 * 爬楼梯实际就是个斐波拉契,有BUG当n过大时候int会越界
 **/

public class ClimbStairs {


    /**
     * 爬楼梯实际就是个斐波拉契、
     *  最后上一步（前n-1步走法） + 最后上两步 前n-2步走法）
     *
     * 优化参考 FibonacciNum
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n <= 2){
            return n;
        }else {
            return climbStairs(n-1) + climbStairs(n-2);
        }
    }


    /**
     * 优化参考 避免重复计算
     */
    private int [] list;

    public int climbStairsOptimization(int n) {
        list = new int[n+1];
        return recu(n);
    }

    private int recu(int n){
        if (n <= 2) {
            return n;
        } else if (list[n] > 0){
            return list[n];
        }else {
            int result = recu(n - 1) + recu(n - 2);
            list[n] = result;
            return result;
        }
    }


}
